1. Field of the Invention
The present invention relates to circuitry and a method for performing a fast mapping from an input value to an output value. The present invention can be applied to register renaming in pipelined loops in a microprocessor.
2. Description of the Related Art
In high performance computing, the requirement for cyclic register renaming arises in the context of software-pipelined loops, where a high rate of instruction execution is usually required of the target machine (e.g. microprocessor). Execution time is often dominated by loop structures within the application program. To permit a high rate of instruction execution a processor may include a plurality of individual execution units, with each individual unit being capable of executing one or more instructions in parallel with the execution of instructions by the other execution units.
Such a plurality of execution units can be used to provide a so-called software pipeline made up of a plurality of individual stages. Each software pipeline stage has no fixed physical correspondence to particular execution units. Rather, when a loop structure in an application program is compiled the machine instructions which make up an individual iteration of the loop are scheduled for execution by the different execution units in accordance with a software pipeline schedule. This schedule is divided up into successive stages and the instructions are scheduled in such a way as to permit a plurality of iterations to be carried out in overlapping manner by the different execution units with a selected loop initiation interval between the initiations of successive iterations. Thus, when a first stage of an iteration i terminates and that iteration enters a second stage, execution of the next iteration i+1 is initiated in a first stage of the iteration i+1. Thus, instructions in the first stage of iteration i+1 are executed in parallel with execution of instructions in the second stage of iteration i.
In such software-pipelined loops there are typically several iterations of a loop in a partial state of completion at each moment. Hence, there may be several live copies of each value computed within the loop. To distinguish between these values, and to identify them relative to the current iteration, requires that the name of each value held in a register must change at well-defined moments during loop execution. These renaming points are known by the compiler, which also determines the register name required within each instruction to access each value depending on the iteration in which it was computed.
The name of a value held in a register is known to the programmer or compiler in terms of the register identifiers within each assembly-code instruction. The purpose of static register renaming is to define a scheme whereby these identifiers are translated at run-time into actual register numbers based on a translation scheme that can be predicted by the programmer or compiler.
For example, if a value X is assigned to register r1 in iteration 1, a typical renaming scheme would make that value available in register r2 in iteration 2 and in register r3 in iteration 3, and so on. It is the responsibility of the compiler or programmer to allocate register identifiers to each value in a way that ensures correct operation of the loop.
In software pipelined loops there are usually loop-variant values, i.e. expressions which must be reevaluated in each different iteration of the loop, that must be communicated between different instructions in the pipeline. To deal with such loop-variant values it is possible to store them in a so-called rotating register file. In this case, each loop-variant value is assigned a logical register number within the rotating register file, and this logical register number does not change from one iteration to the next. Inside the rotating register file each logical register number is mapped to a physical register within the register file and this mapping is rotated each time a new iteration is begun, i.e. each time a pipeline boundary is closed. Accordingly, corresponding instructions in different iterations can all refer to the same logical register number, making the compiled instructions simple, whilst avoiding a value produced by one iteration from being overwritten by a subsequently-executed instruction of a different iteration.
With such a register renaming scheme in operation, before an instruction can be executed by the processor it is first necessary, for each register access within a software-pipelined loop, to perform a register mapping process to translate the register identifiers into actual register numbers. This mapping is done at run time and hence places extra time demands on the processor in a highly time-critical activity. It is therefore desirable that the time taken to perform this mapping is as small as possible.